package Leetcode;

/**
 * 环形列表，返回链表开始入环的第一个节点
 */
public class test142 {

    /**
     * 此题需要一定的智力以及数学思路
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
      ListNode fast=head;
      ListNode low=head;
      while(fast!=null&&fast.next!=null){
          fast=fast.next.next;
          low=low.next;
          //此时快慢指针相遇
          if (fast==low){
              //引入第三个引用，第三个引用一定会和慢指针在环的入口相遇
              ListNode cur=head;
             while (cur!=low){
                 low=low.next;
                 cur=cur.next;
             }
             return low;
          }

      }
      return null;
    }
}
